﻿//被围绕的区域: https://leetcode.cn/problems/surrounded-regions/description/
class Solution {
public:
    int m,n;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[210][210];
    void solve(vector<vector<char>>& board) {
        m=board.size(),n=board[0].size();
        for(int j=0;j<n;j++)
        {
            if(board[0][j]=='O')   dfs(board,0,j);
            if(board[m-1][j]=='O')   dfs(board,m-1,j);
        }
        for(int i=0;i<m;i++)
        {
            if(board[i][0]=='O')   dfs(board,i,0);
            if(board[i][n-1]=='O')  dfs(board,i,n-1);
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(board[i][j]=='O')    board[i][j]='X';
                if(board[i][j]=='.')    board[i][j]='O';
            }
        }
    }
    void dfs(vector<vector<char>>& board,int i,int j)
    {
        board[i][j]='.';
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];    int y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n && board[x][y]=='O')
            {
                //vis[x][y]=true;
                dfs(board,x,y);
            }
        }
    }
};

//太平洋大西洋水流问题: https://leetcode.cn/problems/pacific-atlantic-water-flow/description/
class Solution {
public:
    bool Pvis[210][210];
    bool Avis[210][210];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    vector<vector<int>> ret;
    int m,n;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m=heights.size(),n=heights[0].size();
        for(int i=0;i<m;i++)
        {
            dfs(heights,i,0,Pvis);
            dfs(heights,i,n-1,Avis);
        }
        for(int j=0;j<n;j++)
        {
            dfs(heights,0,j,Pvis);
            dfs(heights,m-1,j,Avis);
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(Pvis[i][j]&&Avis[i][j])
                {
                    ret.push_back({i,j});
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>>& heights,int i,int j,bool vis[210][210])
    {
        vis[i][j]=true;
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k];    int y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n && !vis[x][y] && heights[x][y]>=heights[i][j])
            {
                dfs(heights,x,y,vis);
            }
        }
    }
};